In the context of computer science, a “tree” is a commonly-used data structure that emulates a hierarchical tree structure with a set of linked nodes. A “binary tree” is a more specific type of tree in which the nodes each has at most two child nodes. A “binary decision tree” is a more specific type of binary tree in which the root node and the intermediate nodes each represents a condition having one or two possible outcomes, e.g., the condition is either satisfied or not satisfied, leading to the two child nodes respectively. “Tree traversal” is a process of visiting some or all of the nodes in a tree in a systematic way.
Trees have a great variety of applications. In practice, almost all tree applications require traversing the trees at one time or another and often repeatedly. The complexity of tree traversal increases as the complexity of a tree increases, e.g., as the number of nodes in the tree or the levels of the tree grow. Consequently, tree traversal is often a very expensive process, e.g., in terms of time or resource consumption. In addition, many applications require the traversal of multiple decision trees. For example, in Machine Learning applications, a predictive model often requires the evaluation of multiple decision trees, i.e., traversing multiple decision trees, for any one set of input.